# coding: utf-8
# 桶排序实现（含基数桶、计数桶）

import copy

#计数排序
def countingSort(lst):
    #桶的范围
    minVal=min(lst)
    maxVal=max(lst)
    #准备桶dict
    A={}
    for i in range(minVal,maxVal+1):
        A[i]=0
    for e in lst:
        A[e]+=1
    #倒出结果
    B=[]
    i=minVal
    while i<=maxVal:
        if A[i]>0:
            B.append(i)
            A[i]-=1
        else:
            i+=1
    return B

#取得整数num的pos位数字，pos从0开始
#【int是不可变类型】num和pos是按值传递的，函数内修改不会影响外部，python貌似没有PHP的&地址操作符
def numAt(num,pos):
    # 乘方操作符**
    return int(num/(10**pos))%10
    
#基数排序  https://www.cnblogs.com/sfencs-hcy/p/10616446.html
#准备一个0~9的桶，循环利用就好了
#基数排序只适合正整数，负数和浮点数都不适合！
def radixSort(lst):
    # 拷贝列表
    # lst=copy.copy(lst)
    #取最大值的位数
    maxVal = max(lst)
    #str可以把数值转成字符串
    digitNum=len(str(maxVal))

    for d in range(0,digitNum):
        #准备桶 使用range生成二维数组，range非常好用
        A=[[] for i in range(0,10)]
        #入桶
        for val in lst:
            A[numAt(val,d)].append(val)
        print("第{0}位桶: {1}".format(d,A))
        #出桶，默认顺序index从低到高
        del lst[:]
        for B in A:
            for c in B:
                lst.append(c)
    return lst

#桶排序
#n个桶，桶内部使用list自带的排序算法sort
def bucketSort(lst,n):
    #使用range生成二维数组，0~n-1
    A=[[] for _ in range(n)]
    #入桶
    for val in lst:
        index=int(val/n)
        #不要超过范围
        index=max(0,index)
        index=min(n-1,index)
        A[index].append(val)

    #桶内排序
    #使用enumerate可以同时获得下标和值
    for i,_ in enumerate(A):
        A[i].sort()
    
    #出桶（经典的双循环出桶）
    lst=[]
    for B in A:
        for c in B:
            lst.append(c)
    return lst


lst=[1,11,2,22,3,33,1,2,3,123,456,7899,124]
res=countingSort(lst)
print("countingSort:", res)

num=1234
print("numAt 1:", numAt(num,1))

lst=[1,11,2,22,3,33,1,2,3,123,456,7899,124]
print("radixSort: {0}".format(radixSort(lst)))
print("列表是可变类型，按引用传递 origin: {0}".format(lst))

lst=[1,11,2,22,3,33,1,2,3,123,456,7899,124]
print("bucketSort: {0}".format(bucketSort(lst,4)))
